//给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。 
//
// 给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和 bi的人归入同一组。当可以用
//这种方法将所有人分进两组时，返回 true；否则返回 false。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]
//输出：true
//解释：group1 [1,4], group2 [2,3]
// 
//
// 示例 2： 
//
// 
//输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]
//输出：false
// 
//
// 示例 3： 
//
// 
//输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2000 
// 0 <= dislikes.length <= 10⁴ 
// dislikes[i].length == 2 
// 1 <= dislikes[i][j] <= n 
// ai < bi 
// dislikes 中每一组都 不同 
// 
//
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 👍 183 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class PossibleBipartition {
    public static void main(String[] args) {
        Solution solution = new PossibleBipartition().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        boolean visited[];
        boolean colors[];
        boolean ok;

        public boolean possibleBipartition(int n, int[][] dislikes) {
            visited = new boolean[n + 1];
            colors = new boolean[n + 1];
            ok = true;

            List<Integer>[] graph = buildGraph(dislikes, n);
            // 由于图不连通，所以遍历所有节点
            // 注意编号从1开始
            for (int i = 1; i <= n; i++) {
                if (!visited[i]) {
                    dfs(graph, i);
                    // bfs(graph, i);
                }
            }

            return ok;
        }

        // 构建双向图，注意编号是从1开始的
        public List<Integer>[] buildGraph(int[][] dislikes, int n) {
            List<Integer>[] graph = new LinkedList[n + 1];
            for (int i = 1; i <= n; i++) {
                graph[i] = new LinkedList<Integer>();
            }

            for (int[] dislike : dislikes) {
                int v = dislike[0], t = dislike[1];
                // 注意是无向图
                graph[v].add(t);
                graph[t].add(v);
            }

            return graph;
        }

        public void dfs(List<Integer>[] graph, int s) {
            if (!ok) return;
            visited[s] = true;
            for (int v : graph[s]) {
                if (!visited[v]) {
                    // 进行递归染色
                    colors[v] = !colors[s];
                    dfs(graph, v);
                } else {
                    // 如果访问过，那么判断了两个节点的颜色是否相同，如果相同不满足条件
                    if (colors[v] == colors[s]) ok = false;
                }
            }
        }

        /*public void bfs(List<Integer>[] graph, int s) {
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(s);
            visited[s] = true;

            while (!queue.isEmpty() && ok) {
                Integer poll = queue.poll();
                for (Integer v : graph[poll]) {
                    if (!visited[v]) {
                        colors[v] = !colors[poll];
                        visited[poll] = true;
                        queue.offer(v);
                    }else {
                        if (colors[v] == colors[poll]) ok = false;
                    }
                }
            }
        }*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}
